/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/symmetric-tree
   @Language: C++
   @Datetime: 19-05-27 16:37
   */

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */


// Method 1 , BFS with Recursion, Time 6ms
class Solution {
	bool postorder(TreeNode *left, TreeNode *right){
		if(left==NULL && right==NULL) return true;
		if(left==NULL || right==NULL) return false;
		if(left->val != right->val) return false;
		return postorder(left->left,right->right) && 
			postorder(left->right,right->left);
	}
public:
	/**
	 * @param root: root of the given tree
	 * @return: whether it is a mirror of itself 
	 */
	bool isSymmetric(TreeNode * root) {
		// Write your code here
		if(root==NULL) return true;
		return postorder(root->left,root->right);
	}
};

// Method 2, BFS with queue loop, Time 50ms
class Solution {
public:
	/**
	 * @param root: root of the given tree
	 * @return: whether it is a mirror of itself 
	 */
	bool isSymmetric(TreeNode * root) {
		// Write your code here
		if(root==NULL) return true;
		queue<TreeNode*> left, right;
		for(left.push(root->left), right.push(root->right); left.size() && right.size(); left.pop(),right.pop()){
			TreeNode *l=left.front(), *r=right.front();
			if(l==NULL && r==NULL) continue;
			if(l==NULL || r==NULL) return false;
			if(l->val != r->val) return false;
			left.push(l->left);
			left.push(l->right);
			right.push(r->right);
			right.push(r->left);
		}
		return true;
	}
};
